package com.itzmn.newcode.offer;

import java.util.Scanner;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/14 14:59
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:
 *   高思面试，手撕代码：
 *    输入一串数据组件二叉树，并输出中序遍历
 *    要求： 当输入数据为0时，该节点为NUll，如输入-1，则数据结束
 *
 *    1,2,3,0,5,-1
 *
 *       1
 *    2     3
 *NULL  5
 */
public class BinTreeZhongxu {

    public static void main(String[] args) {

        String[] arrs = {"1", "0"};
        new BinTreeZhongxu().init(arrs);

    }
    public void init(String[] t){

        int[] arrs = new int[t.length];
        for(int i=0;i<t.length;i++){
            arrs[i] = Integer.parseInt(t[i]);
        }
        TreeNode treeNode = new TreeNode(arrs[0]);
        create(arrs,treeNode,1);
        xianxu(treeNode);
    }

    /**
     *  先序遍历
     * @param RoottreeNode
     */
    private  void xianxu(TreeNode RoottreeNode) {

        if (RoottreeNode!=null){
            //查找左节点
            xianxu(RoottreeNode.left);

            System.out.print(RoottreeNode.val+" ");


            //查找右节点
            xianxu(RoottreeNode.right);
        }
    }

    public void create(int[] arrs,TreeNode root,int index){

        boolean left = false;
        boolean right = false;

        if (index*2-1>=arrs.length){
            return;
        }

        int leftval = arrs[index*2-1];


        if (leftval==-1){
            return;
        }

        //根节点的左子树是null并且左边没有被插入过
        if (root.left == null && !left){

            if (leftval != 0){
                TreeNode treeNode = new TreeNode(leftval);
                root.left = treeNode;
            }
            left = true;
        }
        if (index*2>=arrs.length){
            return;
        }
        int rightval = arrs[index*2];
        if (rightval == -1){
            return;
        }
        if (root.right == null && !right){
            if (rightval != 0){
                TreeNode treeNode = new TreeNode(rightval);
                root.right = treeNode;
            }
            right = true;
        }

        if (root.left != null){
            create(arrs,root.left,index+1);
        }
        if (root.right != null){
            create(arrs,root.right,index+1);
        }


    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }


}
